// 前序遍历  中序遍历 后序遍历
// 根据 访问根节点的顺序 ,左子树优先于 右子树
var result = require("./tree.js");
console.log(result);
// 深度优先 DFS (前序中序后序)
// 广度优先 BFS (层序遍历)

// 前序遍历
function preOrderTraverse(root) {
  var res = [];
  // 遍历函数
  function traverse(root) {
    if (root !== null) {
      // 访问传进来的节点
      res.push(root.value);
      if (root.left) {
        // 递归遍历左子树
        traverse(root.left);
      }
      // 递归遍历右子树
      if (root.right) {
        traverse(root, right);
      }
    }
  }
  traverse(root);
  return res;
}

// 后序遍历
function postOrderTraverse(root) {
  var res = [];
  // 遍历函数
  function traverse(root) {
    if (root !== null) {
      if (root.left) {
        traverse(root.left);
      }
      if (root.right) {
        traverse(root.right);
      }
      res.push(root.value);
    }
  }
  traverse(root);
  return res;
}

// 中序遍历
function inOrderTraverse(root) {
  var res = [];
  // 遍历函数
  function traverse(root) {
    if (root !== null) {
      if (root.left) {
        traverse(root.left);
      }
      res.push(root.value);
      if (root.right) {
        traverse(root.right);
      }
    }
  }
  traverse(root);
  return res;
}

// 层序遍历
function levelOrder(root) {
  var res = [];
  // 将本层节点装到一个数组里
  function traverse(root, deepth) {
    if (root !== null) {
      if (!res[deepth]) {
        res[deepth] = [];
      }
      res[deepth].push(root.value);
      if (root.left) {
        traverse(root.left, deepth + 1);
      }
      if (root.right) {
        traverse(root.right, deepth + 1);
      }
    }
  }
  traverse(root, 0);
}
